package org.example.myleet.p1143;

public class Solution {
    /**
     * 12 ms
     * 经典最长公共子序列问题，动态规划，O(mn)
     * dp[i][j]代表的意思是text2的i、text1的j位置所形成的两个字符的最长匹配到的公共子序列
     * 本题动态规划的递推公式
     * 当text1[j]与text2[i]匹配时，在text1[j-1]与text2[i-1]最长匹配子序列长度上再+1
     * 当text1[j]与text2[i]不匹配时，在text1[j-1]与text2[i]，或，text1[j]与text2[i-1]最长匹配子序列长度中选取最长者
     */
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length(), n = text2.length();
        if (m == 0 || n == 0) {
            return 0;
        }
        //匹配情况初始化
        int[][] dp = new int[n][m];
        if (text1.charAt(0) == text2.charAt(0)) {
            dp[0][0] = 1;
        }
        for (int j = 1; j < m; ++j) {
            if (text1.charAt(j) == text2.charAt(0) || dp[0][j-1] > 0) {
                dp[0][j] = 1;
            }
        }
        for (int i = 1; i < n; ++i) {
            if (text1.charAt(0) == text2.charAt(i) || dp[i-1][0] > 0) {
                dp[i][0] = 1;
            }
        }
        //初始化完毕，对矩阵剩余位置用递推公式遍历
        for (int i = 1; i < n; ++i) {
            for (int j = 1; j < m; ++j) {
                if (text1.charAt(j) == text2.charAt(i)) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                    continue;
                }
                dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]);
            }
        }
        return dp[n-1][m-1];
    }
}
